// hash_map extension header
#pragma once
#ifndef _HASH_MAP_
#define _HASH_MAP_
#ifndef RC_INVOKED
#include <xhash>

#pragma pack(push, _CRT_PACKING)
#pragma warning(push, _STL_WARNING_LEVEL)
#pragma warning(disable : _STL_DISABLED_WARNINGS)
_STL_DISABLE_CLANG_WARNINGS
#pragma push_macro("new")
#undef new

#ifndef _SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS
#error <hash_map> is deprecated and will be REMOVED. Please use <unordered_map>. You can define \
_SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS to acknowledge that you have received this warning.
#endif // _SILENCE_STDEXT_HASH_DEPRECATION_WARNINGS

namespace stdext {
    using _STD allocator;
    using _STD enable_if_t;
    using _STD is_constructible_v;
    using _STD pair;
    using _STD swap;
    using _STD _Hash;
    using _STD _Is_nothrow_swappable;
    using _STD _Swap_adl;
    using _STD _Xout_of_range;

    // CLASS TEMPLATE _Hmap_traits
    template <class _Kty, // key type
        class _Ty, // mapped type
        class _Tr, // comparator predicate type
        class _Alloc, // actual allocator type (should be value allocator)
        bool _Mfl> // true if multiple equivalent keys are permitted
    class _Hmap_traits : public _Tr { // traits required to make _Hash behave like a map
    public:
        using key_type            = _Kty;
        using value_type          = pair<const _Kty, _Ty>;
        using _Mutable_value_type = pair<_Kty, _Ty>;
        using key_compare         = _Tr;
        using allocator_type      = _Alloc;
#if _HAS_CXX17
        using node_type =
            _STD _Node_handle<_STD _List_node<value_type, typename _STD allocator_traits<_Alloc>::void_pointer>, _Alloc,
                _STD _Node_handle_map_base, _Kty, _Ty>;
#endif // _HAS_CXX17

        static constexpr bool _Multi    = _Mfl;
        static constexpr bool _Standard = false;

        _Hmap_traits(const _Tr& _Traits = _Tr())
            : _Tr(_Traits), _Max_buckets(0.0F) { // construct with specified comparator
        }

        class value_compare { // functor for comparing two element values
        public:
            using first_argument_type  = value_type;
            using second_argument_type = value_type;
            using result_type          = bool;

            bool operator()(const value_type& _Left,
                const value_type& _Right) const { // test if _Left precedes _Right by comparing just keys
                return _Keycompobj(_Left.first, _Right.first);
            }

            value_compare(const key_compare& _Keycomparg)
                : _Keycompobj(_Keycomparg) { // construct with specified predicate
            }

            key_compare _Keycompobj;
        };

        template <class _Ty1, class _Ty2>
        static const _Kty& _Kfn(const pair<_Ty1, _Ty2>& _Val) { // extract key from element value
            return _Val.first;
        }

        template <class _Ty1, class _Ty2>
        static const _Ty2& _Nonkfn(const pair<_Ty1, _Ty2>& _Val) { // extract non-key from element value
            return _Val.second;
        }

        float& _Get_max_bucket_size() noexcept { // return reference to current maximum bucket size
            return _Max_buckets;
        }

        const float& _Get_max_bucket_size() const noexcept { // return const reference to current maximum bucket size
            return _Max_buckets;
        }

        void swap(_Hmap_traits& _Rhs) _NOEXCEPT_COND(_Is_nothrow_swappable<_Tr>::value) {
            _Swap_adl(static_cast<_Tr&>(*this), static_cast<_Tr&>(_Rhs));
            _STD swap(_Max_buckets, _Rhs._Max_buckets);
        }

        float _Max_buckets; // current maximum bucket size
    };

    // CLASS TEMPLATE hash_map
    template <class _Kty, class _Ty, class _Tr = hash_compare<_Kty, less<_Kty>>,
        class _Alloc = allocator<pair<const _Kty, _Ty>>>
    class hash_map
        : public _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, false>> { // hash table of {key, mapped} values, unique keys
    public:
        using _Mybase         = _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, false>>;
        using key_type        = _Kty;
        using mapped_type     = _Ty;
        using referent_type   = _Ty;
        using key_compare     = _Tr;
        using value_compare   = typename _Mybase::value_compare;
        using value_type      = typename _Mybase::value_type;
        using allocator_type  = typename _Mybase::allocator_type;
        using size_type       = typename _Mybase::size_type;
        using difference_type = typename _Mybase::difference_type;
        using pointer         = typename _Mybase::pointer;
        using const_pointer   = typename _Mybase::const_pointer;
        using reference       = value_type&;
        using const_reference = const value_type&;
        using iterator        = typename _Mybase::iterator;
        using const_iterator  = typename _Mybase::const_iterator;
        using _Pairib         = typename _Mybase::_Pairib;
        using _Alnode         = typename _Mybase::_Alnode;
        using _Alnode_traits  = typename _Mybase::_Alnode_traits;
#if _HAS_CXX17
        using insert_return_type = _STD _Insert_return_type<iterator, typename _Mybase::node_type>;
#endif // _HAS_CXX17

        hash_map() : _Mybase(key_compare(), allocator_type()) { // construct empty map from defaults
        }

        explicit hash_map(const allocator_type& _Al)
            : _Mybase(key_compare(), _Al) { // construct empty map from defaults, allocator
        }

        hash_map(const hash_map& _Right)
            : _Mybase(_Right, _Alnode_traits::select_on_container_copy_construction(
                                  _Right._Getal())) { // construct map by copying _Right
        }

        hash_map(const hash_map& _Right, const allocator_type& _Al)
            : _Mybase(_Right, _Al) { // construct map by copying _Right, allocator
        }

        explicit hash_map(const key_compare& _Traits)
            : _Mybase(_Traits, allocator_type()) { // construct empty map from comparator
        }

        hash_map(const key_compare& _Traits, const allocator_type& _Al)
            : _Mybase(_Traits, _Al) { // construct empty map from comparator and allocator
        }

        template <class _Iter>
        hash_map(_Iter _First, _Iter _Last)
            : _Mybase(key_compare(), allocator_type()) { // construct map from sequence, defaults
            insert(_First, _Last);
        }

        template <class _Iter>
        hash_map(_Iter _First, _Iter _Last, const key_compare& _Traits)
            : _Mybase(_Traits, allocator_type()) { // construct map from sequence, comparator
            insert(_First, _Last);
        }

        template <class _Iter>
        hash_map(_Iter _First, _Iter _Last, const key_compare& _Traits, const allocator_type& _Al)
            : _Mybase(_Traits, _Al) { // construct map from sequence, comparator, and allocator
            insert(_First, _Last);
        }

        hash_map& operator=(const hash_map& _Right) { // assign by copying _Right
            _Mybase::operator=(_Right);
            return *this;
        }

        hash_map(hash_map&& _Right) : _Mybase(_STD move(_Right)) { // construct map by moving _Right
        }

        hash_map(hash_map&& _Right, const allocator_type& _Al)
            : _Mybase(_STD move(_Right), _Al) { // construct map by moving _Right, allocator
        }

        hash_map& operator=(hash_map&& _Right) { // assign by moving _Right
            _Mybase::operator=(_STD move(_Right));
            return *this;
        }

        mapped_type& operator[](key_type&& _Keyval) { // find element matching _Keyval or insert with default mapped
            iterator _Where = this->lower_bound(_Keyval);
            if (_Where == this->end()) {
                _Where = insert(pair<key_type, mapped_type>(_STD move(_Keyval), mapped_type())).first;
            }

            return _Where->second;
        }

        void swap(hash_map& _Right) _NOEXCEPT_COND(noexcept(_Mybase::swap(_Right))) // strengthened
        { // exchange contents with non-movable _Right
            _Mybase::swap(_Right);
        }

        using _Mybase::insert;

        template <class _Valty, class = enable_if_t<is_constructible_v<value_type, _Valty>>>
        _Pairib insert(_Valty&& _Val) { // insert _Val
            return this->emplace(_STD forward<_Valty>(_Val));
        }

        template <class _Valty, class = enable_if_t<is_constructible_v<value_type, _Valty>>>
        iterator insert(const_iterator _Where, _Valty&& _Val) { // insert _Val with hint
            return this->emplace_hint(_Where, _STD forward<_Valty>(_Val));
        }

        hash_map(_STD initializer_list<value_type> _Ilist)
            : _Mybase(key_compare(), allocator_type()) { // construct from initializer_list, defaults
            insert(_Ilist);
        }

        hash_map(_STD initializer_list<value_type> _Ilist, const key_compare& _Pred)
            : _Mybase(_Pred, allocator_type()) { // construct from initializer_list, comparator
            insert(_Ilist);
        }

        hash_map(_STD initializer_list<value_type> _Ilist, const key_compare& _Pred, const allocator_type& _Al)
            : _Mybase(_Pred, _Al) { // construct from initializer_list, comparator, and allocator
            insert(_Ilist);
        }

        hash_map& operator=(_STD initializer_list<value_type> _Ilist) { // assign initializer_list
            this->clear();
            insert(_Ilist);
            return *this;
        }

        mapped_type& operator[](
            const key_type& _Keyval) { // find element matching _Keyval or insert with default mapped
            iterator _Where = this->lower_bound(_Keyval);
            if (_Where == this->end()) {
                _Where = insert(pair<key_type, mapped_type>(_Keyval, mapped_type())).first;
            }

            return _Where->second;
        }

        mapped_type& at(const key_type& _Keyval) { // find element matching _Keyval
            iterator _Where = this->lower_bound(_Keyval);
            if (_Where == this->end()) {
                _Xout_of_range("invalid hash_map<K, T> key");
            }

            return _Where->second;
        }

        const mapped_type& at(const key_type& _Keyval) const { // find element matching _Keyval
            const_iterator _Where = this->lower_bound(_Keyval);
            if (_Where == this->end()) {
                _Xout_of_range("invalid hash_map<K, T> key");
            }

            return _Where->second;
        }

        using reverse_iterator       = _STD reverse_iterator<iterator>;
        using const_reverse_iterator = _STD reverse_iterator<const_iterator>;

        reverse_iterator rbegin() noexcept { // return iterator for beginning of reversed mutable sequence
            return reverse_iterator(this->end());
        }

        const_reverse_iterator rbegin() const
            noexcept { // return iterator for beginning of reversed nonmutable sequence
            return const_reverse_iterator(this->end());
        }

        reverse_iterator rend() noexcept { // return iterator for end of reversed mutable sequence
            return reverse_iterator(this->begin());
        }

        const_reverse_iterator rend() const noexcept { // return iterator for end of reversed nonmutable sequence
            return const_reverse_iterator(this->begin());
        }

        const_reverse_iterator crbegin() const
            noexcept { // return iterator for beginning of reversed nonmutable sequence
            return rbegin();
        }

        const_reverse_iterator crend() const noexcept { // return iterator for end of reversed nonmutable sequence
            return rend();
        }

        using _Mybase::_Unchecked_begin;
        using _Mybase::_Unchecked_end;
    };

    template <class _Kty, class _Ty, class _Tr, class _Alloc>
    inline void swap(hash_map<_Kty, _Ty, _Tr, _Alloc>& _Left, hash_map<_Kty, _Ty, _Tr, _Alloc>& _Right)
        _NOEXCEPT_COND(noexcept(_Left.swap(_Right))) // strengthened
    { // swap _Left and _Right hash_maps
        _Left.swap(_Right);
    }

    template <class _Kty, class _Ty, class _Tr, class _Alloc>
    inline bool operator==(const hash_map<_Kty, _Ty, _Tr, _Alloc>& _Left,
        const hash_map<_Kty, _Ty, _Tr, _Alloc>& _Right) { // test for hash_map equality
        return _STD _Hash_equal(_Left, _Right);
    }

    template <class _Kty, class _Ty, class _Tr, class _Alloc>
    inline bool operator!=(const hash_map<_Kty, _Ty, _Tr, _Alloc>& _Left,
        const hash_map<_Kty, _Ty, _Tr, _Alloc>& _Right) { // test for hash_map inequality
        return !(_Left == _Right);
    }

    // CLASS TEMPLATE hash_multimap
    template <class _Kty, class _Ty, class _Tr = hash_compare<_Kty, less<_Kty>>,
        class _Alloc = allocator<pair<const _Kty, _Ty>>>
    class hash_multimap : public _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, true>> { // hash table of {key, mapped}
                                                                                     // values, non-unique keys
    public:
        using _Mybase         = _Hash<_Hmap_traits<_Kty, _Ty, _Tr, _Alloc, true>>;
        using key_type        = _Kty;
        using mapped_type     = _Ty;
        using referent_type   = _Ty; // old name, magically gone
        using key_compare     = _Tr;
        using value_compare   = typename _Mybase::value_compare;
        using value_type      = typename _Mybase::value_type;
        using allocator_type  = typename _Mybase::allocator_type;
        using size_type       = typename _Mybase::size_type;
        using difference_type = typename _Mybase::difference_type;
        using pointer         = typename _Mybase::pointer;
        using const_pointer   = typename _Mybase::const_pointer;
        using reference       = value_type&;
        using const_reference = const value_type&;
        using iterator        = typename _Mybase::iterator;
        using const_iterator  = typename _Mybase::const_iterator;
        using _Alnode         = typename _Mybase::_Alnode;
        using _Alnode_traits  = typename _Mybase::_Alnode_traits;

        hash_multimap() : _Mybase(key_compare(), allocator_type()) { // construct empty map from defaults
        }

        explicit hash_multimap(const allocator_type& _Al)
            : _Mybase(key_compare(), _Al) { // construct empty map from defaults, allocator
        }

        hash_multimap(const hash_multimap& _Right)
            : _Mybase(_Right, _Alnode_traits::select_on_container_copy_construction(
                                  _Right._Getal())) { // construct map by copying _Right
        }

        hash_multimap(const hash_multimap& _Right, const allocator_type& _Al)
            : _Mybase(_Right, _Al) { // construct map by copying _Right, allocator
        }

        explicit hash_multimap(const key_compare& _Traits)
            : _Mybase(_Traits, allocator_type()) { // construct empty map from comparator
        }

        hash_multimap(const key_compare& _Traits, const allocator_type& _Al)
            : _Mybase(_Traits, _Al) { // construct empty map from comparator and allocator
        }

        template <class _Iter>
        hash_multimap(_Iter _First, _Iter _Last)
            : _Mybase(key_compare(), allocator_type()) { // construct map from sequence, defaults
            insert(_First, _Last);
        }

        template <class _Iter>
        hash_multimap(_Iter _First, _Iter _Last, const key_compare& _Traits)
            : _Mybase(_Traits, allocator_type()) { // construct map from sequence, comparator
            insert(_First, _Last);
        }

        template <class _Iter>
        hash_multimap(_Iter _First, _Iter _Last, const key_compare& _Traits, const allocator_type& _Al)
            : _Mybase(_Traits, _Al) { // construct map from sequence, comparator, and allocator
            insert(_First, _Last);
        }

        hash_multimap& operator=(const hash_multimap& _Right) { // assign by copying _Right

            _Mybase::operator=(_Right);
            return *this;
        }

        hash_multimap(hash_multimap&& _Right) : _Mybase(_STD move(_Right)) { // construct map by moving _Right
        }

        hash_multimap(hash_multimap&& _Right, const allocator_type& _Al)
            : _Mybase(_STD move(_Right), _Al) { // construct map by moving _Right, allocator
        }

        hash_multimap& operator=(hash_multimap&& _Right) { // assign by moving _Right

            _Mybase::operator=(_STD move(_Right));
            return *this;
        }

        void swap(hash_multimap& _Right) _NOEXCEPT_COND(noexcept(_Mybase::swap(_Right))) // strengthened
        { // exchange contents with non-movable _Right
            _Mybase::swap(_Right);
        }

        using _Mybase::insert;

        template <class _Valty, class = enable_if_t<is_constructible_v<value_type, _Valty>>>
        iterator insert(_Valty&& _Val) { // insert _Val
            return this->emplace(_STD forward<_Valty>(_Val)).first;
        }

        template <class _Valty, class = enable_if_t<is_constructible_v<value_type, _Valty>>>
        iterator insert(const_iterator _Where, _Valty&& _Val) { // insert _Val with hint
            return this->emplace_hint(_Where, _STD forward<_Valty>(_Val));
        }

        hash_multimap(_STD initializer_list<value_type> _Ilist)
            : _Mybase(key_compare(), allocator_type()) { // construct from initializer_list, defaults
            insert(_Ilist);
        }

        hash_multimap(_STD initializer_list<value_type> _Ilist, const key_compare& _Pred)
            : _Mybase(_Pred, allocator_type()) { // construct from initializer_list, comparator
            insert(_Ilist);
        }

        hash_multimap(_STD initializer_list<value_type> _Ilist, const key_compare& _Pred, const allocator_type& _Al)
            : _Mybase(_Pred, _Al) { // construct from initializer_list, comparator, and allocator
            insert(_Ilist);
        }

        hash_multimap& operator=(_STD initializer_list<value_type> _Ilist) { // assign initializer_list
            this->clear();
            insert(_Ilist);
            return *this;
        }

        using reverse_iterator       = _STD reverse_iterator<iterator>;
        using const_reverse_iterator = _STD reverse_iterator<const_iterator>;

        reverse_iterator rbegin() noexcept { // return iterator for beginning of reversed mutable sequence
            return reverse_iterator(this->end());
        }

        const_reverse_iterator rbegin() const
            noexcept { // return iterator for beginning of reversed nonmutable sequence
            return const_reverse_iterator(this->end());
        }

        reverse_iterator rend() noexcept { // return iterator for end of reversed mutable sequence
            return reverse_iterator(this->begin());
        }

        const_reverse_iterator rend() const noexcept { // return iterator for end of reversed nonmutable sequence
            return const_reverse_iterator(this->begin());
        }

        const_reverse_iterator crbegin() const
            noexcept { // return iterator for beginning of reversed nonmutable sequence
            return rbegin();
        }

        const_reverse_iterator crend() const noexcept { // return iterator for end of reversed nonmutable sequence
            return rend();
        }

        using _Mybase::_Unchecked_begin;
        using _Mybase::_Unchecked_end;
    };

    template <class _Kty, class _Ty, class _Tr, class _Alloc>
    inline void swap(hash_multimap<_Kty, _Ty, _Tr, _Alloc>& _Left, hash_multimap<_Kty, _Ty, _Tr, _Alloc>& _Right)
        _NOEXCEPT_COND(noexcept(_Left.swap(_Right))) // strengthened
    { // swap _Left and _Right hash_multimaps
        _Left.swap(_Right);
    }

    template <class _Kty, class _Ty, class _Tr, class _Alloc>
    inline bool operator==(const hash_multimap<_Kty, _Ty, _Tr, _Alloc>& _Left,
        const hash_multimap<_Kty, _Ty, _Tr, _Alloc>& _Right) { // test for hash_multimap equality
        return _STD _Hash_equal(_Left, _Right);
    }

    template <class _Kty, class _Ty, class _Tr, class _Alloc>
    inline bool operator!=(const hash_multimap<_Kty, _Ty, _Tr, _Alloc>& _Left,
        const hash_multimap<_Kty, _Ty, _Tr, _Alloc>& _Right) { // test for hash_multimap inequality
        return !(_Left == _Right);
    }
} // namespace stdext
_STD_BEGIN
using stdext::hash_map;
using stdext::hash_multimap;
_STD_END

#pragma pop_macro("new")
_STL_RESTORE_CLANG_WARNINGS
#pragma warning(pop)
#pragma pack(pop)
#endif // RC_INVOKED
#endif // _HASH_MAP_

/*
 * Copyright (c) by P.J. Plauger. All rights reserved.
 * Consult your license regarding permissions and restrictions.
V6.50:0009 */
